# 希尔排序
# by Nasa 2022-5-27
from utils.array_utils import *


def shell(l):
    s = 0
    step = len(l) // 2
    while step >= 1:
        # print(f'use {step}  to sort....')
        for i in range(step, len(l), step):
            n = l[i]
            j = i
            while j > 0 and n < l[j - step]:
                l[j] = l[j - step]
                j -= step
                s += 1
            l[j] = n
        # print(step,l)
        step //= 2
    return s


if __name__ == '__main__':
    ll = [2, 8, 3, 7, 6, 5, 9, 1, 4, 0, -1, 2, -9, 5, 9, 1]
    long = len(ll)
    # # print(long // 2, ll[::long // 2])
    # # print(long // 4, ll[::long // 4])
    # # print(long // 8, ll[::long // 8])
    # # print(long // 16, ll[::long // 16])
    print(shell(ll))
    print(ll)
    print(check_is_sorted(shell))
